package C049;

import java.util.Arrays;

/**
 * ClassName: C06
 * Package: C049
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/2/17 18:24
 * @Version 1.0
 * @Since 1.0
 */
public class C06 {
    public static void main(String[] args) {
        int[] arr = {1,2,1,2,3};
        System.out.println(subarraysWithKDistinct(arr, 2));
        System.out.println(process2(arr, 2));
    }



    public static int subarraysWithKDistinct(int[] nums, int k) {
        return process(nums, k) - process(nums, k - 1);
    }

    static int MAXLEN = 200001;
    static int[] cnt = new int[MAXLEN];

    public static int process(int[] arr, int k) {
        Arrays.fill(cnt, 1, arr.length + 1, 0);
        int collect = 0, ans = 0;
        for (int r = 0, l = 0; r < arr.length; r++) {
            if(cnt[arr[r]]++ == 0) {
                collect ++;
            }

            while(collect > k) {
                if(cnt[arr[l++]]-- == 1) {
                    collect--;
                }
            }
            ans += r - l + 1;
        }
        return ans;
    }


    public static int process2(int[] arr, int k) {
        Arrays.fill(cnt, 1, arr.length + 1, 0);
        int collect = 0, ans = 0;
        for (int r = 0, l = 0; r < arr.length; r++) {
            if (cnt[arr[r]]++ == 0) {
                collect++;
            }

            if(collect == k) {
                ans++;
            }
            while(collect >= k) {
                if(cnt[arr[l++]]-- == 1) {
                    collect--;
                }
            }
        }
        return ans;
    }

}
